#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;



 // Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 



 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int right = 0;
        ListNode* curr = head;
        vector<int> numV;
        while(curr!=NULL){
            numV.push_back(curr->val);
            curr = curr->next;
            ++right;
        }
        TreeNode* root = func(0,right-1,numV);
        return root;
    }

    TreeNode* func(int left ,int right,vector<int>& numV){
        //范围建树
        if(left>right){
            return NULL;
        }
        int mid = (left+right)>>1;
        TreeNode* root = new TreeNode(numV[mid]);
        root->left = func(left,mid-1,numV);
        root->right = func(mid+1,right,numV);
        return root;
    }
};

int main(){
    Solution S;
    ListNode* head = new ListNode(-10);
    head->next = new ListNode(-3);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(5);
    head->next->next->next->next = new ListNode(9);
    TreeNode* root = S.sortedListToBST(head);
    return 0;
}